{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Preorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: preorderTraversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的前序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> ，返回它节点值的 <strong>前序</strong><em> </em>遍历。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg\" style=\"width: 202px; height: 324px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg\" style=\"width: 202px; height: 202px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg\" style=\"width: 202px; height: 202px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-100 <= Node.val <= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>递归算法很简单，你可以通过迭代算法完成吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-preorder-traversal](https://leetcode.cn/problems/binary-tree-preorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-preorder-traversal](https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,3]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = list()\n",
    "\n",
    "        def preorder(ans, node):\n",
    "            if node is None:\n",
    "                return\n",
    "            ans.append(node.val)\n",
    "            preorder(ans, node.left)\n",
    "            preorder(ans, node.right)\n",
    "\n",
    "        preorder(ans, root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        stack = [root]\n",
    "        while len(stack):\n",
    "            root = stack.pop()\n",
    "            while root:\n",
    "                result.append(root.val)\n",
    "                stack.append(root.right)\n",
    "                root = root.left\n",
    "        return(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res, stack = [], []\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            res.append(root.val)\n",
    "            root = root.left\n",
    "        while stack:\n",
    "            n = stack.pop()\n",
    "            r = n.right\n",
    "            while r:\n",
    "                stack.append(r)\n",
    "                res.append(r.val)\n",
    "                r = r.left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "        \n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        self.result.append(root.val)\n",
    "        if root.left:\n",
    "            self.preorderTraversal(root.left)\n",
    "        if root.right:\n",
    "            self.preorderTraversal(root.right)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        # if root == None:\n",
    "        #     return res\n",
    "        stack = []\n",
    "        while root!=None or len(stack)!=0:\n",
    "            if root!=None:\n",
    "                res.append(root.val)\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                root = root.right\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        [1,null,2,3]-->[1,2,3]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        stack = [root]\n",
    "        while len(stack) > 0:\n",
    "            node = stack.pop()\n",
    "            result.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res, stack = [], [(1, root)]\n",
    "        while stack:\n",
    "            p = stack.pop()\n",
    "            if not p[1]: continue\n",
    "            stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':\n",
    "        if not root:\n",
    "            return []\n",
    "        res = list()\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:return []\n",
    "        res,stack=[],[root]\n",
    "\n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        while len(stack) > 0:\n",
    "            curr = stack.pop()\n",
    "            res.append(curr.val)\n",
    "            if curr.right is not None:\n",
    "                stack.append(curr.right)\n",
    "            if curr.left is not None:\n",
    "                stack.append(curr.left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        def _pre_order_tree(root, pre_order_list):\n",
    "            if not root:\n",
    "                return\n",
    "            pre_order_list.append(root.val)\n",
    "            _pre_order_tree(root.left, pre_order_list)\n",
    "            _pre_order_tree(root.right, pre_order_list)\n",
    "        output = list()\n",
    "        _pre_order_tree(root, output)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        p = root\n",
    "        stack = []\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                res.append(p.val)\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop().right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = []\n",
    "        res = []\n",
    "        visited =set()\n",
    "        stack.append(root)\n",
    "        while(stack):\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        ars=[]\n",
    "        while stack:\n",
    "            a = stack.pop()\n",
    "            if a:\n",
    "                ars.append(a.val)\n",
    "                stack.append(a.right)\n",
    "                stack.append(a.left)\n",
    "        return ars\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "                    return []\n",
    "        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        s = []\n",
    "        while s or root:\n",
    "            # 将左边全部入栈,并访问\n",
    "            while root:\n",
    "                s.append(root)\n",
    "                ans.append(root.val)\n",
    "                root = root.left\n",
    "            # 弹出,并访问右子树\n",
    "            node = s.pop()\n",
    "            root = node.right\n",
    "\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        if not root: return []\n",
    "\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            res.append(root.val)\n",
    "            if root.right:\n",
    "                stack.append(root.right)\n",
    "            if root.left:\n",
    "                stack.append(root.left)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []        \n",
    "        res = []\n",
    "        stack = [root]\n",
    "        # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            print(cur)\n",
    "            print(stack)\n",
    "            res.append(cur.val)\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        # 前序递归\n",
    "        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        def travesal(root: TreeNode):\n",
    "            if root == None:\n",
    "                return\n",
    "\n",
    "            res.append(root.val)\n",
    "            travesal(root.left)\n",
    "            travesal(root.right)\n",
    "\n",
    "        travesal(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.preorderTraversal(root.left)\n",
    "        right = self.preorderTraversal(root.right)\n",
    "        return [root.val] + left + right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        res = []\n",
    "\n",
    "        while stack :\n",
    "            print(stack)\n",
    "            tmp = stack.pop()\n",
    "            res.append(tmp.val)\n",
    "\n",
    "            if tmp.right:\n",
    "                stack.append(tmp.right)\n",
    "            if tmp.left:\n",
    "                stack.append(tmp.left)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "from multiprocessing import ProcessError\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\r\n",
    "        results = []\r\n",
    "        stack = []\r\n",
    "        while root or stack:\r\n",
    "\r\n",
    "            while root:\r\n",
    "                results.append(root.val)\r\n",
    "                stack.append(root)\r\n",
    "                root = root.left\r\n",
    "            \r\n",
    "            root = stack.pop()\r\n",
    "            root = root.right\r\n",
    "\r\n",
    "        return results\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # def preorder(root: TreeNode):\n",
    "        #     if not root:\n",
    "        #         return\n",
    "        #     res.append(root.val)\n",
    "        #     preorder(root.left)\n",
    "        #     preorder(root.right)\n",
    "        \n",
    "        # res = list()\n",
    "        # preorder(root)\n",
    "        # return res\n",
    "        stack = []\n",
    "        result = []\n",
    "        node = root\n",
    "        while node or stack:\n",
    "            while node:\n",
    "                result.append(node.val)\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            node = node.right\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        def helper(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            res.append(root.val)\n",
    "            helper(root.left)\n",
    "            \n",
    "            helper(root.right)\n",
    "\n",
    "        helper(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(node: Optional[TreeNode], result: List[int]) -> None:\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            result.append(node.val)\n",
    "            dfs(node.left, res)\n",
    "            dfs(node.right, res)\n",
    "\n",
    "        res = []\n",
    "        dfs(root, res)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
